import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int m = 0, n = 0;
    Queue<int[]> q = new LinkedList<>();

    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;

        //用来标记grid中的元素是否被遍历到
        boolean[][] temp = new boolean[m][n];

        int ret = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !temp[i][j]) {
                    //bfs
                    ret++;
                    bfs(grid, temp, i, j);
                }
            }
        }

        return ret;
    }

    public void bfs(char[][] grid, boolean[][] temp, int i, int j) {
        q.offer(new int[]{i, j});
        while (!q.isEmpty()) {
            int[] arr = q.poll();
            int x = arr[0];
            int y = arr[1];
            temp[x][y] = true;
            //遍历四个方向
            for (int k = 0; k < 4; k++) {
                int xx = x + dx[k];
                int yy = y + dy[k];
                if (xx >= 0 && yy >= 0 && xx < m && yy < n && !temp[xx][yy] && grid[xx][yy] == '1') {
                    q.offer(new int[]{xx, yy});
                }
            }
        }
    }

}
